package com.sky.alogrithm.chapter02_sort;

import static com.sky.alogrithm.chapter02_sort.Merge.merge;


public class Merge2 {

    //归并所需的辅助数组
    private static Comparable[] aux;

    public static void sort(Comparable[] a){
        aux = new Comparable[a.length];
        sort(a, 0, a.length - 1);
    }


    /**
     * 自顶向下的归并排序
     * 原理：将两个子数组排序，就能够通过归并两个子数组将两个数组排序
     */
    private static void sort(Comparable[] a, int lo, int hi){
        if(hi <= lo){
            return;
        }
        int mid = lo + (hi - lo) / 2;
        sort(a, lo, mid); //将左半边排序
        sort(a, mid + 1, hi); //将右半边排序
        merge(a, lo, mid, hi); //归并结果
    }

    /**
     * 自底向上的归并排序
     * @param a
     */
    public static void sort2(Comparable[] a){
        int N = a.length;
        aux = new Comparable[N];
        for(int sz = 1; sz < N; sz = sz + sz){
            for(int lo = 0; lo < N - sz; lo += sz + sz){
                merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));
            }
        }
    }
}
